本文章不讲解 vDom 实现，mount 挂载，以及 render 函数。只讨论三种 diff 算法。VNode 类型不考虑 component、functional-component、Fragment、Teleport。只考虑 Element 和 Text。此文章全部代码可参考该项目。

下面的 diff 算法中会出现几个方法，在这里进行罗列，并说明其功能

mount(vnode, parent, [refNode]): 通过vnode生成真实的DOM节点。parent为其父级的真实 DOM 节点，refNode为真实的DOM节点，其父级节点为parent。如果refNode不为空，vnode生成的DOM节点就会插入到refNode之前；如果refNode为空，那么vnode生成的DOM节点就作为最后一个子节点插入到parent中

patch(prevNode, nextNode, parent): 可以简单的理解为给当前DOM节点进行更新，并且调用diff算法对比自身的子节点;

React 的思路是递增法。通过对比新的列表中的节点，在原本的列表中的位置是否是递增，来判断当前节点是否需要移动。

来看这样一个例子。

nextList为新的列表，prevList为旧列表。这个例子我们一眼能看出来，新列表是不需要进行移动的。下面我用react的递增思想，解释一下为什么新列表中的节点不需要移动。

我们首先遍历nextList，并且找到每一个节点，在prevList中的位置。

找到位置以后，与上一个节点的位置进行对比，如果当前的位置大于上一个位置，说明当前节点不需要移动。因此我们要定义一个lastIndex来记录上一个节点的位置。

在上面的例子中，nextList每个节点在prevList的位置为0 1 2 3。每一项都要比前一项要大，所以不需要移动，这就是react的diff算法的原理。

在上一小节中，我们是通过对比值是否相等，查找的对应位置。但是在 vdom 中，每一个节点都是一个 vNode，我们应该如何进行判断呢？

答案就是key，我们通过对每个节点的key进行赋值，并且让处于同一children数组下的vnode的key都不相同，以此来确定每个节点的唯一性，并进行新旧列表的对比。

首先我们先明确一点，移动节点所指的节点是DOM节点。vnode.el指向该节点对应的真实DOM节点。patch方法会将更新过后的DOM节点，赋值给新的vnode的el属性。

为了画图方便，我们用key的值来表示vnode节点。为了行文方便，我们把key值为a的vnode简写为vnode-a，vnode-a对应的真实 DOM 节点为DOM-A

我们来将上图的例子代入reactDiff中执行。我们遍历新列表，并查找vnode在旧列表中的位置。当遍历到vnode-d时，之前遍历在旧列表的位置为0 < 2 < 3，说明A C D这三个节点都是不需要移动的。此时lastIndex = 3, 并进入下一次循环，发现vnode-b在旧列表的index为1，1 < 3，说明DOM-B要移动。

通过观察我们能发现，只需要把DOM-B移动到DOM-D之后就可以了。也就是找到需要移动的 VNode，我们称该 VNode 为 α，将 α 对应的真实的 DOM 节点移动到，α 在新列表中的前一个 VNode 对应的真实 DOM 的后面。

在上述的例子中，就是将vnode-b对应的真实 DOM 节点DOM-B, 移动到vnode-b在新列表中的前一个VNode——vnode-d对应的真实 DOM 节点DOM-D的后面。

为什么是这样移动的呢？首先我们列表是从头到尾遍历的。这就意味着对于当前VNode节点来说，该节点之前的所有节点都是排好序的，如果该节点需要移动，那么只需要将 DOM 节点移动到前一个vnode节点之后就可以，因为在新列表中vnode的顺序就是这样的。

上一小节我们只讲了如何移动节点，但是忽略了另外一种情况，就是在新列表中有全新的VNode节点，在旧列表中找不到。遇到这种情况，我们需要根据新的VNode节点生成DOM节点，并插入DOM树中。

至此，我们面临两个问题：1.如何发现全新的节点、2. 生成的DOM节点插入到哪里

我们先来解决第一个问题，找节点还是比较简单的，我们定义一个find变量值为false。如果在旧列表找到了key 相同的vnode，就将find的值改为true。当遍历结束后判断find值，如果为false，说明当前节点为新节点。

找到新节点后，下一步就是插入到哪里了，这里的逻辑其实是和移动节点的逻辑是一样的。我们观察上图可以发现，新的vnode-c是紧跟在vnode-b后面的，并且vnode-b的 DOM 节点——DOM-B是已经排好序的，所以我们只需要将vnode-c生成的 DOM 节点插入到DOM-B之后就可以了。

但是这里有一种特殊情况需要注意，就是新的节点位于新列表的第一个，这时候我们需要找到旧列表第一个节点，将新节点插入到原来第一个节点之前就可以了。

我们根据四个指针找到四个节点，然后进行对比，那么如何对比呢？我们按照以下四个步骤进行对比

使用以上四步进行对比，去寻找key相同的可复用的节点，当在某一步中找到了则停止后面的寻找。具体对比顺序如下图

对比顺序代码结构如下:

当对比时找到了可复用的节点，我们还是先patch给元素打补丁，然后将指针进行前/后移一位指针。根据对比节点的不同，我们移动的指针和方向也不同，具体规则如下：

在小节的开头，提到了要让指针向内靠拢，所以我们需要循环。循环停止的条件是当其中一个列表的节点全部遍历完成，代码如下

至此整体的循环我们就全部完成了，下面我们需要考虑这样两个问题：

我们来解决第一个问题：什么情况下需要移动，我们还是以上图为例。

当我们在第一个循环时，在第四步发现旧列表的尾节点oldEndNode与新列表的头节点newStartNode的key相同，是可复用的DOM节点。通过观察我们可以发现，原本在旧列表末尾的节点，却是新列表中的开头节点，没有人比他更靠前，因为他是第一个，所以我们只需要把当前的节点移动到原本旧列表中的第一个节点之前，让它成为第一个节点即可。

然后我们进入第二次循环，我们在第二步发现，旧列表的尾节点oldEndNode和新列表的尾节点newEndNode为复用节点。原本在旧列表中就是尾节点，在新列表中也是尾节点，说明该节点不需要移动，所以我们什么都不需要做。

同理，如果是旧列表的头节点oldStartNode和新列表的头节点newStartNode为复用节点，我们也什么都不需要做。

进入第三次循环，我们在第三部发现，旧列表的头节点oldStartNode和新列表的尾节点newEndNode为复用节点。到这一步聪明如你肯定就一眼可以看出来了，我们只要将DOM-A移动到DOM-B后面就可以了。

依照惯例我们还是解释一下，原本旧列表中是头节点，然后在新列表中是尾节点。那么只要在旧列表中把当前的节点移动到原本尾节点的后面，就可以了。

OK，进入最后一个循环。在第一步旧列表头节点oldStartNode与新列表头节点newStartNode位置相同，所以啥也不用做。然后结束循环，这就是Vue2 双端比较的原理。

上一小节，我们讲了双端比较的原理，但是有一种特殊情况，当四次对比都没找到复用节点时，我们只能拿新列表的第一个节点去旧列表中找与其key相同的节点。

。

找节点的时候其实会有两种情况：一种在旧列表中找到了，另一种情况是没找到。我们先以上图为例，说一下找到的情况。

当我们在旧列表中找到对应的VNode，我们只需要将找到的节点的DOM元素，移动到开头就可以了。这里的逻辑其实和第四步的逻辑是一样的，只不过第四步是移动的尾节点，这里是移动找到的节点。DOM移动后，由我们将旧列表中的节点改为undefined，这是至关重要的一步，因为我们已经做了节点的移动了所以我们不需要进行再次的对比了。最后我们将头指针newStartIndex向后移一位。

如果在旧列表中没有找到复用节点呢？很简单，直接创建一个新的节点放到最前面就可以了，然后后移头指针newStartIndex。

最后当旧列表遍历到undefind时就跳过当前节点。

我们先来看一个例子

这个例子非常简单，几次循环都是尾节点相同，尾指针一直向前移动，直到循环结束，如下图

此时oldEndIndex以及小于了oldStartIndex，但是新列表中还有剩余的节点，我们只需要将剩余的节点依次插入到oldStartNode的DOM之前就可以了。为什么是插入oldStartNode之前呢？原因是剩余的节点在新列表的位置是位于oldStartNode之前的，如果剩余节点是在oldStartNode之后，oldStartNode就会先行对比，这个需要思考一下，其实还是与第四步的思路一样。

至此双端比较全部完成，以下是全部代码。

这时候，我们就需要考虑边界情况了，这里有两种情况。一种是j > prevEnd；另一种是j > nextEnd。

我们以这张图为例，此时j > prevEnd且j nextEnd时，我们把旧列表中j到prevEnd之间的节点删除就可以了。

那么这个source数组，是要做什么的呢？他就是来做新旧节点的对应关系的，我们将新节点在旧列表的位置存储在该数组中，我们在根据source计算出它的最长递增子序列用于移动 DOM 节点。为此，我们先建立一个对象存储当前新列表中的节点与index的关系，再去旧列表中去找位置。

在找节点时要注意，如果旧节点在新列表中没有的话，直接删除就好。除此之外，我们还需要一个数量表示记录我们已经patch过的节点，如果数量已经与新列表剩余的节点数量一样，那么剩下的旧节点我们就直接删除了就可以了

找到位置后，我们观察这个重新赋值后的source，我们可以看出，如果是全新的节点的话，其在source数组中对应的值就是初始的-1，通过这一步我们可以区分出来哪个为全新的节点，哪个是可复用的。

其次，我们要判断是否需要移动。那么如何判断移动呢？很简单，和React一样我们用递增法，如果我们找到的index是一直递增的，说明不需要移动任何节点。我们通过设置一个变量来保存是否需要移动的状态。

判断完是否需要移动后，我们就需要考虑如何移动了。一旦需要进行 DOM 移动，我们首先要做的就是找到source的最长递增子序列。

什么是最长递增子序列：给定一个数值序列，找到它的一个子序列，并且子序列中的值是递增的，子序列中的元素在原序列中不一定连续。

例如给定数值序列为：[ 0, 8, 4, 12 ]。

那么它的最长递增子序列就是：[0, 8, 12]。

当然答案可能有多种情况，例如：[0, 4, 12] 也是可以的。

我们在下一节单独讲解最长递增子序列

上面的代码中，我们调用lis 函数求出数组source的最长递增子序列为[ 0, 1 ]。我们知道 source 数组的值为 [2, 3, 1, -1]，很显然最长递增子序列应该是[ 2, 3 ]，但为什么计算出的结果是[ 0, 1 ]呢？其实[ 0, 1 ]代表的是最长递增子序列中的各个元素在source数组中的位置索引，如下图所示：

我们根据source，对新列表进行重新编号，并找出了最长递增子序列。

我们从后向前进行遍历source每一项。此时会出现三种情况：

说完了需要移动的情况，再说说不需要移动的情况。如果不需要移动的话，我们只需要判断是否有全新的节点给他添加进去就可以了。具体代码如下：

至此vue3.0的 diff 完成。

leetcode 有原题，官方解析很清晰，看不懂我讲的可以去看看官方解析。

我们以该数组为例

我们可以使用动态规划的思想考虑这个问题。动态规划的思想是将一个大的问题分解成多个小的子问题，并尝试得到这些子问题的最优解，子问题的最优解有可能会在更大的问题中被利用，这样通过小问题的最优解最终求得大问题的最优解。

我们先假设只有一个值的数组[13]，那么该数组的最长递增子序列就是[13]自己本身，其长度为1。那么我们认为每一项的递增序列的长度值均为 1

那么我们这次给数组增加一个值[7, 13], 由于7 < 13，所以该数组的最长递增子序列是[7, 13]，那么该长度为2。那么我们是否可以认为，当[7]小于[13]时，以[7]为头的递增序列的长度是，[7]的长度和[13]的长度的和，即1 + 1 = 2。

ok，我们基于这种思想来给计算一下该数组。我们先将每个值的初始赋值为1

首先 7 < 13 那么7对应的长度就是13的长度再加 1，1 + 1 = 2

继续，我们对比8。我们首先和7比，发现不满足递增，但是没关系我们还可以继续和13比，8 < 13满足递增，那么8的长度也是13的长度在加一，长度为2

我们再对比3，我们先让其与8进行对比，3 < 8，那么3的长度是8的长度加一，此时3的长度为3。但是还没结束，我们还需要让3与7对比。同样3 < 7，此时我们需要在计算出一个长度是7的长度加一同样是3，我们对比两个长度，如果原本的长度没有本次计算出的长度值大的话，我们进行替换，反之则我们保留原本的值。由于3 === 3，我们选择不替换。最后，我们让3与13进行对比，同样的3 < 13，此时计算出的长度为2，比原本的长度3要小，我们选择保留原本的值。

之后的计算依次类推，最后的结果是这样的

我们从中取最大的值4，该值代表的最长递增子序列的个数。代码如下：

本文作者：京东科技 孙延哲 更多数科技术最佳实践&创新成果，请关注“京东数科技术说”微信公众号